package 动态规划;

public class 最长回文子序列 {
    //动态规划的思想
    class Solution{
        public int longestPalindromeSubseq(String s){
            int len = s.length();
            int[][] dp = new int[len + 1][len+1];
            //从后面往前面遍历保证不漏
            for (int i = len-1; i >= 0; i--) {
              dp[i][i] = 1;//初始化
                for (int j = 0; j <len; j++) {
                    if (s.charAt(i) == s.charAt(j)){
                        dp[i][j] = dp[i+1][j-1];
                    }else {
                        dp[i][j] = Math.max(dp[i+1][j],Math.max(dp[i][j-1],dp[i][j]));
                    }
                }
            }
            return dp[0][len-1];
        }
    }
}
